package com.sjf.day02.Search;

import java.util.Arrays;

/**
 * 斐波那契查找算法
 *
 * @author <huangtang>
 * @since 2021/12/31 11:08
 **/
public class FibSearch {

    public static final int maxSize = 20;

    public static void main(String[] args) {
        int[] arr = {1,8,10,89,1000,1234};

        System.out.println(fibSearch(arr,1234));
    }

    /**
        需要用到mid=low+F(k-1)-1,需要使用斐波那契数列，所以先得到一个斐波那契数列
     **/
    public static int[] fib(){
      int[] f = new int[maxSize];
      f[0] = 1; f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i-1]+f[i-2];
        }
        return f;
    }

    /**
     * 斐波那契查找算法
     * 使用非递归的方式实现
     * @param a 数组
     * @param key 需要查找的关键码
     * @return
     */
    public static int fibSearch(int[] a,int key){
        int low = 0;
        int high = a.length-1;
        int k = 0;//斐波那契黄金分隔值的下标
        int mid = 0;//存放mid=low+F(k-1)-1;
        int f[] = fib(); //获取到斐波那契数列
        while(high > f[k] - 1) k++;
        //因为f[k]可能大于数组的长度，因此需要使用构建一个新数组，使a指向该新数组
        int[] temp = Arrays.copyOf(a,f[k]);
        //需要使用a数组最后的数填充temp
        // temp = {1,8,10,89,1000,1234,0,0,0} =>  {1,8,10,89,1000,1234,1234,1234,1234}
        for (int i = high+1; i < temp.length; i++) {
            temp[i] = a[high];
        }
        //使用while循环查找key
        while(low <= high){
            mid = low+f[k-1]-1;
            if(key < temp[mid]) {
                //应该继续向mid的左侧查找
                high = mid - 1;
                k--; //
            }else if(key > temp[mid]){
                //应该继续向mid的右侧查找
                low = mid + 1;
                k-=2;
            }else{
                //找到
                return Math.min(mid, high);
            }
        }
        return -1;
    }
}
